P4778 Counting swaps

对于每个位置 $i$ , 我们向 $p_i$ 连一条边。 结合题意可知，一个合法的排列，是一个由 $n$ 个自环组成的图。

但现在会形成多个环，不妨记环的数量为 $k$ ， 第 $i$ 个环的大小为 $s_i$（包括自环）。

我们现在要做的，就是将这 $k$ 个环拆成 $n$ 个自环。

显然，对于一个大小为 $s$ 的环，拆成自环至少需要 $s-1$次操作。

记 $w_n(x,y)$ , 表示将 $n$ 个点的环 ， 拆成 $x$ 个点的环 + $y$个点的环的方案数。

显然有

$w_n(x,y)= \begin{cases} \frac{n}{2} & x=y\\ n & x \not= y \end{cases} (x+y=n)$

记 $f_n$ 表示大小为 $n$ 的环的拆分方案数（$f_1=1$） , 则根据多重集的排列公式得：

$f_n=\sum_{x+y=n}^{x \le\frac{n}{2}}w_n(x,y) \times f_x \times f_y \times \frac{ (n-2)! }{(x-1)! (y-1)!}$

这样递推的复杂度是 $\Theta(n^2)$ 的 ，给一份代码：

f[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
		for( int x = 1 ; x <= i / 2 ; x ++ ) {
			int y = i - x , t = x == y ? i / 2 : i;
			f[ i ] += t * f[ x ] * f[ y ] * ( Fac[ i - 2 ] / Fac[ x - 1 ] / Fac[ y - 1 ] );
		}
		printf("%d %d\n", i , f[ i ] );
	}

经过找规律，我们发现，$f_i=i^{i-2}$，现在就可以$\Theta(nlogn)$求出$f_i$了。

答案也是一个多重集，可以简单求出

$Ans=(\prod_{i=1}^k f[s_i]) \times (\frac{(n-k)!}{\prod_{i=1}^k(s_i-1)!})$

#include <cstdio>
#include <cstring>
using namespace std;
#define Mod 1000000009

const int MAXN = 100000;
int t , n , p[ MAXN + 5 ] , s[ MAXN + 5 ] , k;
bool vis[ MAXN + 5 ];

int Quick_pow( int x , int po ) {
	int Ans = 1;
	while( po ) {
		if( po % 2 ) Ans = 1ll * Ans * x % Mod;
		x = 1ll * x * x % Mod;
		po /= 2;
	}
	return Ans;
}
int Inv( int x ) {
	return Quick_pow( x , Mod - 2 );
} 

int dfs( int u ) {
	if( vis[ u ] ) return 0;
	vis[ u ] = 1;
	return dfs( p[ u ] ) + 1;
}

int f[ MAXN + 5 ] , Fac[ MAXN + 5 ] , InvFac[ MAXN + 5 ];
void Init( ) {
	f[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ )
		f[ i ] = Quick_pow( i , i - 2 );
	
	Fac[ 0 ] = 1; 
	for( int i = 1 ; i <= MAXN ; i ++ )
		Fac[ i ] = 1ll * Fac[ i - 1 ] * i % Mod;
		
	InvFac[ MAXN ] = Inv( Fac[ MAXN ] );
	for( int i = MAXN - 1 ; i >= 0 ; i -- )
		InvFac[ i ] = 1ll * InvFac[ i + 1 ] * ( i + 1 ) % Mod;
}
int main( ) {
	Init( ); 
	scanf("%d",&t);
	while( t -- ) {
		k = 0;
		memset( vis , 0 , sizeof( vis ) );
		memset( s , 0 , sizeof( s ) );
		
		scanf("%d",&n);
		for( int i = 1 ; i <= n ; i ++ )
			scanf("%d",&p[ i ]);
		for( int i = 1 ; i <= n ; i ++ )
			if( !vis[ i ] ) s[ ++ k ] = dfs( i );
		
		int p1 = 1 , p2 = 1 , p3 = Fac[ n - k ];
		for( int i = 1 ; i <= k ; i ++ ) {
			p1 = 1ll * p1 * f[ s[ i ] ] % Mod;
			p2 = 1ll * p2 * Fac[ s[ i ] - 1 ] % Mod;
		}
		printf("%d\n", 1ll * p1 * Inv( p2 ) % Mod * p3 % Mod );
	}
	return 0;
}